package com.hoppinzq.algorithm.graph;

import com.hoppinzq.algorithm.stackAndQueue.MyQueue;

/**
 * 3
 * 广度优先搜索
 * 优先找兄弟结点，然后找子节点
 */
public class BreadthFirstSearch {

    private int count;
    private boolean[] marked;
    private MyQueue<Integer> queue;

    public BreadthFirstSearch(MyGraph graph,int v){
        marked=new boolean[graph.V()];
        count=0;
        queue=new MyQueue<>();
        bfs(graph,v);
    }

    private void bfs(MyGraph graph,int v){
        marked[v]=true;
        queue.enQueue(v);
        while(!queue.isEmpty()){
            MyQueue<Integer> broNode=graph.getQueue(queue.deQueue());
            for (Integer i:broNode) {
                if(!marked[i]){
                    bfs(graph,i);
                }
            }
        }
        count++;
    }

    /**
     * 指定顶点w是否与v顶点连通？
     * @param w
     * @return
     */
    public boolean marked(int w){
        return marked[w];
    }

    /**
     * 返回指定顶点连通的顶点数目
     * @return
     */
    public int getCount(){
        return count;
    }

}
